package com.leetcode.listnode.demo3;

/**
 * @Author Zan
 * @Create 2024/5/13 9:10
 * @ClassName: Test
 * @Description : https://leetcode.cn/problems/reverse-linked-list/description/  反转链表
 */
public class Test {
    public static void main(String[] args) {

    }
}

// 使用双指针法，调整指向的箭头
class Solution {
    public ListNode reverseList(ListNode head) {
        // 修改链表的方向
        ListNode pre = null;
        ListNode current = head;

        while (current != null) {
            // 保存一下后面这个链表，不然会找不到
            ListNode temp = current.next;
            current.next = pre;
            pre = current;
            current = temp;
        }
        return pre;
    }
}

// 递归
class Solution2 {
    public ListNode reverseList(ListNode head) {
        return reverse(null, head);
    }

    private ListNode reverse(ListNode prev, ListNode cur) {
        if (cur == null) {
            return prev;
        }
        ListNode temp = null;
        temp = cur.next;// 先保存下一个节点
        cur.next = prev;// 反转
        // 更新prev、cur位置
        return reverse(cur, temp);
    }
}

class ListNode {
    int val;
    ListNode next;

    public ListNode() {
    }
    public ListNode(int val) {
        this.val = val;
    }
    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
